# -*- coding: utf-8 -*-

"""剑指 Offer II 031. 最近最少使用缓存
运用所掌握的数据结构，设计和实现一个  LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put

进阶：是否可以在 O(1) 时间复杂度内完成这两种操作？"""


class Node():
    def __init__(self, key, val, prev=None, next=None) -> None:
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next


class LRUCache:
    """本体的关键在如何维护最近最少使用关系，一个容易想到的方法是，使用链表的前后关系来维护最近最少。
    同时为了方便 put 到 key 存在的节点时操作的方便，可以维护一个双向链表，在头尾分别设置哨兵节点。
    为了 使用时查询方便，可以维护一个 {key-node} 的哈希字典"""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashdict = {}
        self.cache = Node(0, 0)
        self.cache.next = Node(0, 0, self.cache)
        self.size = 0
        self.tail = self.cache.next

    def get(self, key: int) -> int:
        if key in self.hashdict.keys():
            mvnode = self.hashdict[key]
            mvnode.prev.next, mvnode.next.prev = mvnode.next, mvnode.prev
            last = self.tail.prev
            last.next, mvnode.prev = mvnode, last
            mvnode.next, self.tail.prev = self.tail, mvnode
            return mvnode.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashdict.keys():
            mvnode = self.hashdict[key]
            mvnode.prev.next, mvnode.next.prev = mvnode.next, mvnode.prev
            last = self.tail.prev
            last.next, mvnode.prev = mvnode, last
            mvnode.next, self.tail.prev = self.tail, mvnode
            mvnode.val = value
        else:
            nwnode = Node(key, value)
            last = self.tail.prev
            last.next, nwnode.prev = nwnode, last
            nwnode.next, self.tail.prev = self.tail, nwnode
            self.hashdict[key] = nwnode
            self.size += 1

        if self.size > self.capacity and self.size > 0:
            rmnode = self.cache.next
            rmkey = rmnode.key
            self.cache.next, rmnode.next.prev = rmnode.next, self.cache
            del self.hashdict[rmkey]
            self.size -= 1

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

if __name__ == '__main__':
    lRUCache = LRUCache(2)
    print(lRUCache.put(1, 1))
    print(lRUCache.put(2, 2))
    print(lRUCache.get(1))
    print(lRUCache.put(3, 3))
    print(lRUCache.get(2))
    print(lRUCache.put(4, 4))
    print(lRUCache.get(1))
    print(lRUCache.get(3))
    print(lRUCache.get(4))
